package com.leetcode.partition18;

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2022/2/4 14:03
 */
public class LC1786从第一个节点出发到最后一个节点的受限路径数 {

    private static final int N = (int) (2e4 + 10), M = 8 * N, mod = (int) (1e9 + 7);
    private static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    private static int[] dist = new int[N], f = new int[N];
    private static boolean[] st = new boolean[N];
    private static PriorityQueue<int[]> heap = new PriorityQueue<>(N, (o1, o2) -> Integer.compare(o1[1], o2[1]));

    private static int n = 0, m = 0, idx = 1;
    private static int[][] nodes = new int[N][2];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            edges[i] = new int[]{a, b, c};
        }
        writer.write(countRestrictedPaths(n, edges) + "\n");
        writer.flush();
    }

    public static int countRestrictedPaths(int _n, int[][] edges) {
        n = _n;
        m = 2 * edges.length;
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1], c = edge[2];
            add(a, b, c);
            add(b, a, c);
        }
        return dijkstra();
    }

    private static int dijkstra() {
        for (int i = 0; i < N; i++) dist[i] = Integer.MAX_VALUE;
        dist[n] = 0;
        heap.add(new int[]{n, 0});
         while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int u = cur[0];
            if (st[u]) continue;
            st[u] = true;
            for (int i = h[u]; i != 0; i = ne[i]) {
                int v = e[i];
                if (dist[v] > dist[u] + w[i]) {
                    dist[v] = dist[u] + w[i];
                    heap.add(new int[]{v, dist[v]});
                }
            }
        }
         //排序使dp的更新顺序满足一个拓扑序
        for (int i = 0; i < n; i++) nodes[i] = new int[]{i + 1, dist[i + 1]};
        Arrays.sort(nodes, 0, n, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        //按照拓扑序进行dp
        f[n] = 1;
        for (int i = 0; i < n; i++) {
            int u = nodes[i][0], d = nodes[i][1];
            for (int j = h[u]; j != 0; j = ne[j]) {
                int v = e[j];
                //u 节点状态由 v 节点状态转移而来，且要保证计算 u 时，v 已经计算完毕
                if (d > dist[v]) f[u] = (f[u] + f[v]) % mod;
            }
            //第 1 个节点不一定是距离第 n 个节点最远的点，但我们只需要 f[1]，可以直接跳出循环
            if (u == 1) break;
        }
        return f[1];
    }

    private static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx;
        w[idx++] = c;
    }
}
